package com.zhugang.week14.concurrent;

import org.junit.Test;

import java.util.List;
import java.util.concurrent.atomic.AtomicStampedReference;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static org.junit.Assert.assertEquals;

/**
 * @program algorithms
 * @description: LockFreeStack
 * @author: chanzhugang
 * @create: 2022/09/15 21:45
 */
public class LockFreeStack<T> {

    static class Node<T> {
        Node<T> next;
        T value;

        public Node(T value) {
            this.value = value;
            this.next = null;
        }
    }


    AtomicStampedReference<Node<T>> head;

    public LockFreeStack() {
        Node headNode = new Node<T>(null);
        head = new AtomicStampedReference<>(headNode, 0);
    }

    public void push(T v) {
        Node newNode = new Node<T>(v);
        while (true) {
            int stamp = head.getStamp();
            Node<T> ref = head.getReference();
            newNode.next = ref;
            if (head.compareAndSet(ref, newNode, stamp, stamp + 1)) {
                return;
            }
        }

    }

    public T pop() {
        while (true) {
            int stamp = head.getStamp();
            Node<T> ref = head.getReference();
            if (ref.next == null) {
                return null;
            }
            Node next = ref.next;
//            head.compareAndSet(ref, next, stamp, stamp+1);
//            return ref.value;
            if (head.compareAndSet(ref, next, stamp, stamp + 1)) {
                return ref.value;
            }
        }
    }


    @Test
    public void testSingle() {
        LockFreeStack<Integer> stack = new LockFreeStack<Integer>();
        for (int i = 0; i < 100; i++) {
            stack.push(i);
        }

        Integer j = null;
        Integer i = 99;
        while ((j = stack.pop()) != null) {
            assertEquals(j + "", i-- + "");
        }
    }

    @Test
    public void testMultiThreads() throws InterruptedException {
        LockFreeStack stack = new LockFreeStack<Integer>();
        List<Thread> list = IntStream.range(0, 16)
                .mapToObj(i -> {
                    Thread t = new Thread(() -> {
                        // 线程id
                        System.out.println(Thread.currentThread().getId());
                        for (int j = 0; j < 100; j++) {
                            try {
                                stack.push(j);
                                Thread.sleep(1);
                                stack.push(j);
                                Thread.sleep(1);
                                stack.pop();
                                Thread.sleep(1);
                            } catch (InterruptedException e) {
                                e.printStackTrace();
                            }
                        }
                    });
                    t.start();
                    return t;
                }).collect(Collectors.toList());
        list.forEach(t -> {
            // 启动16个线程，每个线程push 加100
            System.out.println("wait join..");
            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        Integer c = 0;
        while (stack.pop() != null) {
            c++;
        }
        assertEquals(c + "", "1600");
    }
}